Search Results

Documents authored by Maneth, Sebastian

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.134
When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?

Authors: Sebastian Maneth and Helmut Seidl

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We consider two natural subclasses of deterministic top-down tree-to-tree transducers, namely, linear and uniform-copying transducers. For both classes we show that it is decidable whether the translation of a transducer with look-ahead can be realized by a transducer without look-ahead. The transducers constructed in this way, may still make use of inspection, i.e., have an additional tree automaton restricting the domain. We provide a second procedure which decides whether inspection can be removed and if so, constructs an equivalent transducer without inspection. The construction relies on a fixpoint algorithm that determines inspection requirements and on dedicated earliest normal forms for linear as well as uniform-copying transducers which can be constructed in polynomial time. As a consequence, equivalence of these transducers can be decided in polynomial time. Applying these results to deterministic bottom-up transducers, we obtain that it is decidable whether or not their translations can be realized by deterministic uniform-copying top-down transducers without look-ahead (but with inspection) - or without both look-ahead and inspection.
Cite as

Sebastian Maneth and Helmut Seidl. When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{maneth_et_al:LIPIcs.ICALP.2020.134,
  author =	{Maneth, Sebastian and Seidl, Helmut},
  title =	{{When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{134:1--134:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.134},
  URN =		{urn:nbn:de:0030-drops-125416},
  doi =		{10.4230/LIPIcs.ICALP.2020.134},
  annote =	{Keywords: Top-Down Tree Transducers, Earliest Transformation, Linear Transducers, Uniform-copying Transucers, Removal of Look-ahead, Removal of Inspection}
}
Document
DOI: 10.4230/DagRep.7.4.23
Formal Methods of Transformations (Dagstuhl Seminar 17142)

Authors: Emmanuel Filiot, Sebastian Maneth, and Helmut Seidl

Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)

Abstract
The goal of this Dagstuhl seminar was to gather researchers working on the theory and practice of transformations (also know as transductions) of word and tree structures, which are realised by transducers (automata with outputs). This seminar was motivated by recent advances and breakthrough results, both in the settings of words and trees.
Cite as

Emmanuel Filiot, Sebastian Maneth, and Helmut Seidl. Formal Methods of Transformations (Dagstuhl Seminar 17142). In Dagstuhl Reports, Volume 7, Issue 4, pp. 23-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{filiot_et_al:DagRep.7.4.23,
  author =	{Filiot, Emmanuel and Maneth, Sebastian and Seidl, Helmut},
  title =	{{Formal Methods of Transformations (Dagstuhl Seminar 17142)}},
  pages =	{23--37},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{4},
  editor =	{Filiot, Emmanuel and Maneth, Sebastian and Seidl, Helmut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.4.23},
  URN =		{urn:nbn:de:0030-drops-75462},
  doi =		{10.4230/DagRep.7.4.23},
  annote =	{Keywords: string transducers, tree transducers, expressiveness, complexity}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2017.18
Compression of Unordered XML Trees

Authors: Markus Lohrey, Sebastian Maneth, and Carl Philipp Reh

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract
Many XML documents are data-centric and do not make use of the inherent document order. Can we provide stronger compression for such documents through giving up order? We first consider compression via minimal dags (directed acyclic graphs) and study the worst case ratio of the size of the ordered dag divided by the size of the unordered dag, where the worst case is taken for all trees of size n. We prove that this worst case ratio is n / log n for the edge size and n log log n / log n for the node size. In experiments we compare several known compressors on the original document tree versus on a canonical version obtained by length-lexicographical sorting of subtrees. For some documents this difference is surprisingly large: reverse binary dags can be smaller by a factor of 3.7 and other compressors can be smaller by factors of up to 190.
Cite as

Markus Lohrey, Sebastian Maneth, and Carl Philipp Reh. Compression of Unordered XML Trees. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.ICDT.2017.18,
  author =	{Lohrey, Markus and Maneth, Sebastian and Reh, Carl Philipp},
  title =	{{Compression of Unordered XML Trees}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.18},
  URN =		{urn:nbn:de:0030-drops-70584},
  doi =		{10.4230/LIPIcs.ICDT.2017.18},
  annote =	{Keywords: tree compression, directed acyclic graphs, XML}
}
Document
DOI: 10.4230/DagRep.6.10.99
Computation over Compressed Structured Data (Dagstuhl Seminar 16431)

Authors: Philip Bille, Markus Lohrey, Sebastian Maneth, and Gonzalo Navarro

Published in: Dagstuhl Reports, Volume 6, Issue 10 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16431 "Computation over Compressed Structured Data".
Cite as

Philip Bille, Markus Lohrey, Sebastian Maneth, and Gonzalo Navarro. Computation over Compressed Structured Data (Dagstuhl Seminar 16431). In Dagstuhl Reports, Volume 6, Issue 10, pp. 99-119, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{bille_et_al:DagRep.6.10.99,
  author =	{Bille, Philip and Lohrey, Markus and Maneth, Sebastian and Navarro, Gonzalo},
  title =	{{Computation over Compressed Structured Data (Dagstuhl Seminar 16431)}},
  pages =	{99--119},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{10},
  editor =	{Bille, Philip and Lohrey, Markus and Maneth, Sebastian and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.10.99},
  URN =		{urn:nbn:de:0030-drops-69521},
  doi =		{10.4230/DagRep.6.10.99},
  annote =	{Keywords: algorithms on compressed structures, data compression, indexing, straight- line programs}
}
Document
DOI: 10.4230/DagRep.3.6.22
Indexes and Computation over Compressed Structured Data (Dagstuhl Seminar 13232)

Authors: Sebastian Maneth and Gonzalo Navarro

Published in: Dagstuhl Reports, Volume 3, Issue 6 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13232 "Indexes and Computation over Compressed Structured Data".
Cite as

Sebastian Maneth and Gonzalo Navarro. Indexes and Computation over Compressed Structured Data (Dagstuhl Seminar 13232). In Dagstuhl Reports, Volume 3, Issue 6, pp. 22-37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{maneth_et_al:DagRep.3.6.22,
  author =	{Maneth, Sebastian and Navarro, Gonzalo},
  title =	{{Indexes and Computation over Compressed Structured Data (Dagstuhl Seminar 13232)}},
  pages =	{22--37},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{6},
  editor =	{Maneth, Sebastian and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.6.22},
  URN =		{urn:nbn:de:0030-drops-42558},
  doi =		{10.4230/DagRep.3.6.22},
  annote =	{Keywords: Compression; Indexes; Data Structures}
}
Document
DOI: 10.4230/DagRep.3.5.1
Tree Transducers and Formal Methods (Dagstuhl Seminar 13192)

Authors: Sebastian Maneth and Helmut Seidl

Published in: Dagstuhl Reports, Volume 3, Issue 5 (2013)

Abstract
The aim of this Dagstuhl Seminar was to bring together researchers from various research areas related to the theory and application of tree transducers. Recently, interest in tree transducers has been revived due to surprising new applications in areas such as XML databases, security verification, programming language theory, and linguistics. This seminar therefore aimed to inspire the exchange of theoretical results and information regarding the practical requirements related to tree transducers.
Cite as

Sebastian Maneth and Helmut Seidl. Tree Transducers and Formal Methods (Dagstuhl Seminar 13192). In Dagstuhl Reports, Volume 3, Issue 5, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{maneth_et_al:DagRep.3.5.1,
  author =	{Maneth, Sebastian and Seidl, Helmut},
  title =	{{Tree Transducers and Formal Methods (Dagstuhl Seminar 13192)}},
  pages =	{1--18},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{5},
  editor =	{Maneth, Sebastian and Seidl, Helmut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.5.1},
  URN =		{urn:nbn:de:0030-drops-41769},
  doi =		{10.4230/DagRep.3.5.1},
  annote =	{Keywords: tree transducers, expressiveness, complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.RTA.2012.5
Dictionary-Based Tree Compression (Invited Talk)

Authors: Sebastian Maneth

Published in: LIPIcs, Volume 15, 23rd International Conference on Rewriting Techniques and Applications (RTA'12) (2012)

Abstract
Trees are a ubiquitous data structure in computer science. LISP, for instance, was designed to manipulate nested lists, that is, ordered unranked trees. Already at that time, DAGs were used to detect common subexpression, a process known as "hash consing." In a DAG every distinct subtree is represented only once (but can be referenced many times) and hence it constitutes a dictionary-based compression method for ordered trees. In our compression scenario we distinguish two kinds of ordered trees: binary and unranked. The latter appear naturally as representation of XML document structures. We survey these dictionary-based compression methods for ordered trees: (1) DAGs, (2) hybrid DAGs, (3) straight-line context-free tree grammars ("SLT grammars"). We compare the minimal DAG of an unranked tree with the minimal DAG of its binary tree encoding. The latter is obtained by identifying first children of the unranked tree with left children of the binary tree, and next-siblings with the right children. For XML document trees, unranked DAGs are usually smaller than encoded binary DAGs. We show that this holds for arbitrary unranked trees, on average. We also present the "hybrid DAG"; its size lower-bounds those of the binary and unranked DAGs. Finding a smallest SLT grammar for a given tree is NP-complete. We discuss two linear-time approximation algorithms: BPLEX and TreeRePair. For typical XML document trees, TreeRePair produces SLT grammars that are only one fourth of the size of the minimal DAG, and which contain approximately 3$% of the edges of the original tree. As far as we know, this gives rise to the smallest existing pointer-based tree representation. We show that some basic algorithms can be computed directly on the compressed trees, without prior decompression. Examples include the execution of different kinds of tree automata, and the real-time traversal of the original tree. It is even possible to evaluate simple XPath queries directly on the SLT grammars, using deterministic node-selecting tree automata. In this way, impressive speed-ups are achieved over existing XPath evaluators, while at the same time the memory requirement is slashed to only a few percent. For more complex XPath queries that require nondeterministic node-selecting tree automata, efficient evaluation over SLT grammars remains a difficult challenge.
Cite as

Sebastian Maneth. Dictionary-Based Tree Compression (Invited Talk). In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, p. 5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{maneth:LIPIcs.RTA.2012.5,
  author =	{Maneth, Sebastian},
  title =	{{Dictionary-Based Tree Compression}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12)},
  pages =	{5--5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Tiwari, Ashish},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2012.5},
  URN =		{urn:nbn:de:0030-drops-34802},
  doi =		{10.4230/LIPIcs.RTA.2012.5},
  annote =	{Keywords: Tree grammars, tree automata, straight-line programs}
}
Document
DOI: 10.4230/LIPIcs.RTA.2011.51
First-Order Unification on Compressed Terms

Authors: Adrià Gascón, Sebastian Maneth, and Lander Ramos

Published in: LIPIcs, Volume 10, 22nd International Conference on Rewriting Techniques and Applications (RTA'11) (2011)

Abstract
Singleton Tree Grammars (STGs) have recently drawn considerable attention. They generalize the sharing of subtrees known from DAGs to sharing of connected subgraphs. This allows to obtain smaller in-memory representations of trees than with DAGs. In the past years some important tree algorithms were proved to perform efficiently (without decompression) over STGs; e.g., type checking, equivalence checking, and unification. We present a tool that implements an extension of the unification algorithm for STGs. This algorithm makes extensive use of equivalence checking. For the latter we implemented two variants, the classical exact one and a recent randomized one. Our experiments show that the randomized algorithm performs better. The running times are also compared to those of unification over uncompressed trees.
Cite as

Adrià Gascón, Sebastian Maneth, and Lander Ramos. First-Order Unification on Compressed Terms. In 22nd International Conference on Rewriting Techniques and Applications (RTA'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 10, pp. 51-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gascon_et_al:LIPIcs.RTA.2011.51,
  author =	{Gasc\'{o}n, Adri\`{a} and Maneth, Sebastian and Ramos, Lander},
  title =	{{First-Order Unification on Compressed Terms}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{51--60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Schmidt-Schauss, Manfred},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2011.51},
  URN =		{urn:nbn:de:0030-drops-31263},
  doi =		{10.4230/LIPIcs.RTA.2011.51},
  annote =	{Keywords: unification, matching, grammars, compression, STG, system C++}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1757
The Complexity of Tree Transducer Output Languages

Authors: Kazuhiro Inaba and Sebastian Maneth

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
Two complexity results are shown for the output languages generated by compositions of macro tree transducers. They are in $\NSPACE(n)$ and hence are context-sensitive, and the class is NP-complete.
Cite as

Kazuhiro Inaba and Sebastian Maneth. The Complexity of Tree Transducer Output Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 244-255, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{inaba_et_al:LIPIcs.FSTTCS.2008.1757,
  author =	{Inaba, Kazuhiro and Maneth, Sebastian},
  title =	{{The Complexity of Tree Transducer Output Languages}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{244--255},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1757},
  URN =		{urn:nbn:de:0030-drops-17570},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1757},
  annote =	{Keywords: Complexity, Tree Transducer, OI-hierarchy, Context-Sensitive}
}
Document
DOI: 10.4230/DagSemProc.08261.1
08261 Abstracts Collection – Structure-Based Compression of Complex Massive Data

Authors: Stefan Böttcher, Markus Lohrey, Sebastian Maneth, and Wojciech Rytter

Published in: Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008)

Abstract
From June 22, 2008 to June 27, 2008 the Dagstuhl Seminar 08261 ``Structure-Based Compression of Complex Massive Data'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Stefan Böttcher, Markus Lohrey, Sebastian Maneth, and Wojciech Rytter. 08261 Abstracts Collection – Structure-Based Compression of Complex Massive Data. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bottcher_et_al:DagSemProc.08261.1,
  author =	{B\"{o}ttcher, Stefan and Lohrey, Markus and Maneth, Sebastian and Rytter, Wojciech},
  title =	{{08261 Abstracts Collection – Structure-Based Compression of Complex Massive Data}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.1},
  URN =		{urn:nbn:de:0030-drops-16948},
  doi =		{10.4230/DagSemProc.08261.1},
  annote =	{Keywords: Data compression, algorithms for compressed strings and trees, XML-compression}
}
Document
DOI: 10.4230/DagSemProc.08261.2
08261 Executive Summary – Structure-Based Compression of Complex Massive Data

Authors: Stefan Böttcher, Markus Lohrey, Sebastian Maneth, and Wojciech Rytter

Published in: Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008)

Abstract
From 22nd June to 27th of June 2008, the Dagstuhl Seminar ``08261 Structure-Based Compression of Complex Massive Data'' took place at the Conference and Research Center (IBFI) in Dagstuhl. 22 researchers with interests in theory and application of compression and computation on compressed structures met to present their current work and to discuss future directions.
Cite as

Stefan Böttcher, Markus Lohrey, Sebastian Maneth, and Wojciech Rytter. 08261 Executive Summary – Structure-Based Compression of Complex Massive Data. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bottcher_et_al:DagSemProc.08261.2,
  author =	{B\"{o}ttcher, Stefan and Lohrey, Markus and Maneth, Sebastian and Rytter, Wojciech},
  title =	{{08261 Executive Summary – Structure-Based Compression of Complex Massive Data}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.2},
  URN =		{urn:nbn:de:0030-drops-16814},
  doi =		{10.4230/DagSemProc.08261.2},
  annote =	{Keywords: Compression, Succinct Data Structure, Pattern Matching, Text Search, XML Query}
}
Document
DOI: 10.4230/DagSemProc.08261.6
An In-Memory XQuery/XPath Engine over a Compressed Structured Text Representation

Authors: Angela Bonifati, Gregory Leighton, Veli Mäkinen, Sebastian Maneth, Gonzalo Navarro, and Andrea Pugliese

Published in: Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008)

Abstract
We describe the architecture and main algorithmic design decisions for an XQuery/XPath processing engine over XML collections which will be represented using a self-indexing approach, that is, a compressed representation that will allow for basic searching and navigational operations in compressed form. The goal is a structure that occupies little space and thus permits manipulating large collections in main memory.
Cite as

Angela Bonifati, Gregory Leighton, Veli Mäkinen, Sebastian Maneth, Gonzalo Navarro, and Andrea Pugliese. An In-Memory XQuery/XPath Engine over a Compressed Structured Text Representation. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bonifati_et_al:DagSemProc.08261.6,
  author =	{Bonifati, Angela and Leighton, Gregory and M\"{a}kinen, Veli and Maneth, Sebastian and Navarro, Gonzalo and Pugliese, Andrea},
  title =	{{An In-Memory XQuery/XPath Engine over a Compressed Structured Text Representation}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.6},
  URN =		{urn:nbn:de:0030-drops-16776},
  doi =		{10.4230/DagSemProc.08261.6},
  annote =	{Keywords: Compressed self-index, compressed XML representation, XPath, XQuery}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact